home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / os2 / pccts.zip / FSET2.C < prev    next >
C/C++ Source or Header  |  1992-12-08  |  18KB  |  749 lines
  1. /*
  2.  * fset2.c
  3.  *
  4.  * Compute FIRST sets for full LL(k)
  5.  *
  6.  * SOFTWARE RIGHTS
  7.  *
  8.  * We reserve no LEGAL rights to the Purdue Compiler Construction Tool
  9.  * Set (PCCTS) -- PCCTS is in the public domain.  An individual or
  10.  * company may do whatever they wish with source code distributed with
  11.  * PCCTS or the code generated by PCCTS, including the incorporation of
  12.  * PCCTS, or its output, into commerical software.
  13.  * 
  14.  * We encourage users to develop software with PCCTS.  However, we do ask
  15.  * that credit is given to us for developing PCCTS.  By "credit",
  16.  * we mean that if you incorporate our source code into one of your
  17.  * programs (commercial product, research project, or otherwise) that you
  18.  * acknowledge this fact somewhere in the documentation, research report,
  19.  * etc...  If you like PCCTS and have developed a nice tool with the
  20.  * output, please mention that you developed it using PCCTS.  In
  21.  * addition, we ask that this header remain intact in our source code.
  22.  * As long as these guidelines are kept, we expect to continue enhancing
  23.  * this system and expect to make other tools available as they are
  24.  * completed.
  25.  *
  26.  * ANTLR 1.06
  27.  * Terence Parr
  28.  * Purdue University
  29.  * 1989-1992
  30.  */
  31. #include <stdio.h>
  32. #ifdef __STDC__
  33. #include <stdarg.h>
  34. #else
  35. #include <varargs.h>
  36. #endif
  37. #include "set.h"
  38. #include "syn.h"
  39. #include "hash.h"
  40. #include "generic.h"
  41. #include "dlgdef.h"
  42.  
  43. extern char tokens[];
  44.  
  45. /* ick! globals.  Used by permute() to track which elements of a set have been used */
  46. static int *index;
  47. static set *fset;
  48. static unsigned **ftbl;
  49. static set *constrain; /* pts into fset. constrains tToken() to 'constrain' */
  50. int ConstrainSearch;
  51. static int maxk; /* set to initial k upon tree construction request */
  52. static Tree *FreeList = NULL;
  53.  
  54. #ifdef __STDC__
  55. Tree *tmake(Tree *root, ...);
  56. #else
  57. Tree *tmake();
  58. #endif
  59.  
  60. /* Do root
  61.  * Then each sibling
  62.  */
  63. void
  64. preorder(tree)
  65. Tree *tree;
  66. {
  67.     if ( tree == NULL ) return;
  68.     if ( tree->down != NULL ) fprintf(stderr, " (");
  69.     if ( tree->token == ALT ) fprintf(stderr, " J");
  70.     else fprintf(stderr, " %s", TerminalString(tree->token));
  71.     if ( tree->token==EpToken ) fprintf(stderr, "(%d)", tree->v.rk);
  72.     preorder(tree->down);
  73.     if ( tree->down != NULL ) fprintf(stderr, " )");
  74.     preorder(tree->right);
  75. }
  76.  
  77. /* check the depth of each primary sibling to see that it is exactly
  78.  * k deep. e.g.;
  79.  *
  80.  *    ALT
  81.  *   |
  82.  *   A ------- B
  83.  *   |         |
  84.  *   C -- D    E
  85.  *
  86.  * Remove all branches <= k deep.
  87.  *
  88.  * Added by TJP 9-23-92 to correct the LL(k) constraint mechanism to work.
  89.  */
  90. Tree *
  91. prune(t, k)
  92. Tree *t;
  93. int k;
  94. {
  95.     if ( t == NULL ) return NULL;
  96.     if ( t->token == ALT ) fatal("prune: ALT node in FIRST tree");
  97.     t->right = prune(t->right, k);
  98.     t->down = prune(t->down, k-1);
  99.     if ( t->down == NULL && k > 1 )
  100.     {
  101.         Tree *r = t->right;
  102.         t->right = NULL;
  103.         Tfree(t);
  104.         return r;
  105.     }
  106.     return t;
  107. }
  108.  
  109. /* build a tree (root child1 child2 ... NULL) */
  110. #ifdef __STDC__
  111. Tree *tmake(Tree *root, ...)
  112. #else
  113. Tree *tmake(va_alist)
  114. va_dcl
  115. #endif
  116. {
  117.     va_list ap;
  118.     Tree *child, *sibling=NULL, *tail;
  119. #ifndef __STDC__
  120.     Tree *root;
  121. #endif
  122. #ifdef __STDC__
  123.     require(root!=NULL, "tmake: NULL root impossible");
  124. #endif
  125.  
  126. #ifdef __STDC__
  127.     va_start(ap, root);
  128. #else
  129.     va_start(ap);
  130.     root = va_arg(ap, Tree *);
  131. #endif
  132.     child = va_arg(ap, Tree *);
  133.     while ( child != NULL )
  134.     {
  135.         if ( sibling == NULL ) sibling = tail = child;
  136.         else {tail->right = child; tail = child;}
  137.         child = va_arg(ap, Tree *);
  138.     }
  139.     root->down = sibling;
  140.     va_end(ap);
  141.     return root;
  142. }
  143.  
  144. Tree *
  145. tnode(tok)
  146. int tok;
  147. {
  148.     Tree *p, *newblk;
  149.     static int n=0;
  150.     
  151.     if ( FreeList == NULL )
  152.     {
  153.         /*fprintf(stderr, "tnode: %d more nodes\n", TreeBlockAllocSize);*/
  154.         if ( TreeResourceLimit > 0 )
  155.         {
  156.             if ( (n+TreeBlockAllocSize) >= TreeResourceLimit )
  157.             {
  158.                 fprintf(stderr, ErrHdr, FileStr[CurAmbigfile], CurAmbigline);
  159.                 fprintf(stderr, " hit analysis resource limit while analyzing alts %d and %d %s\n",
  160.                                 CurAmbigAlt1,
  161.                                 CurAmbigAlt2,
  162.                                 CurAmbigbtype);
  163.                 exit(-1);
  164.             }
  165.         }
  166.         newblk = (Tree *)calloc(TreeBlockAllocSize, sizeof(Tree));
  167.         if ( newblk == NULL )
  168.         {
  169.             fprintf(stderr, ErrHdr, FileStr[CurAmbigfile], CurAmbigline);
  170.             fprintf(stderr, " out of memory while analyzing alts %d and %d %s\n",
  171.                             CurAmbigAlt1,
  172.                             CurAmbigAlt2,
  173.                             CurAmbigbtype);
  174.             exit(-1);
  175.         }
  176.         n += TreeBlockAllocSize;
  177.         for (p=newblk; p<&(newblk[TreeBlockAllocSize]); p++)
  178.         {
  179.             p->right = FreeList;    /* add all new Tree nodes to Free List */
  180.             FreeList = p;
  181.         }
  182.     }
  183.     p = FreeList;
  184.     FreeList = FreeList->right;        /* remove a tree node */
  185.     p->right = NULL;                /* zero out ptrs */
  186.     p->down = NULL;
  187.     p->token = tok;
  188.     return p;
  189. }
  190.  
  191. static Tree *
  192. eofnode(k)
  193. int k;
  194. {
  195.     Tree *t=NULL;
  196.     int i;
  197.  
  198.     for (i=1; i<=k; i++)
  199.     {
  200.         t = tmake(tnode(EofToken), t, NULL);
  201.     }
  202.     return t;
  203. }
  204.  
  205.  
  206.  
  207. void
  208. tfree(t)
  209. Tree *t;
  210. {
  211.     if ( t!=NULL )
  212.     {
  213.         t->right = FreeList;
  214.         FreeList = t;
  215.     }
  216. }
  217.  
  218. /* tree duplicate */
  219. Tree *
  220. tdup(t)
  221. Tree *t;
  222. {
  223.     Tree *u;
  224.     
  225.     if ( t == NULL ) return NULL;
  226.     u = tnode(t->token);
  227.     u->v.rk = t->v.rk;
  228.     u->right = tdup(t->right);
  229.     u->down = tdup(t->down);
  230.     return u;
  231. }
  232.  
  233. Tree *
  234. tappend(t,u)
  235. Tree *t, *u;
  236. {
  237.     Tree *w;
  238.  
  239.     /*fprintf(stderr, "tappend(");
  240.     preorder(t); fprintf(stderr, ",");
  241.     preorder(u); fprintf(stderr, " )\n");*/
  242.     if ( t == NULL ) return u;
  243.     if ( t->token == ALT && t->right == NULL ) return tappend(t->down, u);
  244.     for (w=t; w->right!=NULL; w=w->right) {;}
  245.     w->right = u;
  246.     return t;
  247. }
  248.  
  249. /* dealloc all nodes in a tree */
  250. void
  251. Tfree(t)
  252. Tree *t;
  253. {
  254.     if ( t == NULL ) return;
  255.     Tfree( t->down );
  256.     Tfree( t->right );
  257.     tfree( t );
  258. }
  259.  
  260. /* find all children (alts) of t that require remaining_k nodes to be LL_k
  261.  * tokens long.
  262.  *
  263.  * t-->o
  264.  *     |
  265.  *     a1--a2--...--an        <-- LL(1) tokens
  266.  *     |   |        |
  267.  *     b1  b2  ...  bn        <-- LL(2) tokens
  268.  *     |   |        |
  269.  *     .   .        .
  270.  *     .   .        .
  271.  *     z1  z2  ...  zn        <-- LL(LL_k) tokens
  272.  *
  273.  * We look for all [Ep] needing remaining_k nodes and replace with u.
  274.  * u is not destroyed or actually used by the tree (a copy is made).
  275.  */
  276. Tree *
  277. tlink(t,u,remaining_k)
  278. Tree *t, *u;
  279. int remaining_k;
  280. {
  281.     Tree *p;
  282.     require(remaining_k!=0, "tlink: bad tree");
  283.  
  284.     if ( t==NULL ) return NULL;
  285.     /*fprintf(stderr, "tlink: u is:"); preorder(u); fprintf(stderr, "\n");*/
  286.     if ( t->token == EpToken && t->v.rk == remaining_k )
  287.     {
  288.         require(t->down==NULL, "tlink: invalid tree");
  289.         if ( u == NULL ) return t->right;
  290.         p = tdup( u );
  291.         p->right = t->right;
  292.         tfree( t );
  293.         return p;
  294.     }
  295.     t->down = tlink(t->down, u, remaining_k);
  296.     t->right = tlink(t->right, u, remaining_k);
  297.     return t;
  298. }
  299.  
  300. /* remove as many ALT nodes as possible while still maintaining semantics */
  301. Tree *
  302. tshrink(t)
  303. Tree *t;
  304. {
  305.     if ( t == NULL ) return NULL;
  306.     t->down = tshrink( t->down );
  307.     t->right = tshrink( t->right );
  308.     if ( t->down == NULL )
  309.     {
  310.         if ( t->token == ALT )
  311.         {
  312.             Tree *u = t->right;
  313.             tfree(t);
  314.             return u;            /* remove useless alts */
  315.         }
  316.         return t;
  317.     }
  318.  
  319.     /* (? (ALT (? ...)) s) ==> (? (? ...) s) where s = sibling, ? = match any */
  320.     if ( t->token == ALT && t->down->right == NULL)
  321.     {
  322.         Tree *u = t->down;
  323.         u->right = t->right;
  324.         tfree( t );
  325.         return u;
  326.     }
  327.     /* (? (A (ALT t)) s) ==> (? (A t) s) where A is a token; s,t siblings */
  328.     if ( t->token != ALT && t->down->token == ALT && t->down->right == NULL )
  329.     {
  330.         Tree *u = t->down->down;
  331.         tfree( t->down );
  332.         t->down = u;
  333.         return t;
  334.     }
  335.     return t;
  336. }
  337.  
  338. Tree *
  339. tflatten(t)
  340. Tree *t;
  341. {
  342.     if ( t == NULL ) return NULL;
  343.     t->down = tflatten( t->down );
  344.     t->right = tflatten( t->right );
  345.     if ( t->down == NULL ) return t;
  346.     
  347.     if ( t->token == ALT )
  348.     {
  349.         Tree *u;
  350.         /* find tail of children */
  351.         for (u=t->down; u->right!=NULL; u=u->right) {;}
  352.         u->right = t->right;
  353.         u = t->down;
  354.         tfree( t );
  355.         return u;
  356.     }
  357.     return t;
  358. }
  359.  
  360. Tree *
  361. tJunc(p,k,rk)
  362. Junction *p;
  363. int k;
  364. set *rk;
  365. {
  366.     Tree *t=NULL, *u=NULL;
  367.     Junction *alt;
  368.     Tree *tail, *r;
  369.  
  370. #ifdef DBG_TRAV
  371.     fprintf(stderr, "tJunc(%d): %s in rule %s\n", k,
  372.             decodeJType[p->jtype], ((Junction *)p)->rname);
  373. #endif
  374.     if ( p->jtype==aLoopBlk || p->jtype==RuleBlk ||
  375.          p->jtype==aPlusBlk || p->jtype==aSubBlk || p->jtype==aOptBlk )
  376.     {
  377.         if ( p->jtype!=aSubBlk && p->jtype!=aOptBlk ) {
  378.             require(p->lock!=NULL, "rJunc: lock array is NULL");
  379.             if ( p->lock[k] ) return NULL;
  380.             p->lock[k] = TRUE;
  381.         }
  382.         TRAV(p->p1, k, rk, tail);
  383.         if ( p->jtype==RuleBlk ) {p->lock[k] = FALSE; return tail;}
  384.         r = tmake(tnode(ALT), tail, NULL);
  385.         for (alt=(Junction *)p->p2; alt!=NULL; alt = (Junction *)alt->p2)
  386.         {
  387.             if ( tail==NULL ) {TRAV(alt->p1, k, rk, tail); r->down = tail;}
  388.             else
  389.             {
  390.                 TRAV(alt->p1, k, rk, tail->right);
  391.                 /* TJP -- lost info when tail->right was NULL
  392.                 tail = tail->right;*/
  393.                 if ( tail->right != NULL ) tail = tail->right;
  394.             }
  395.         }
  396.         if ( p->jtype!=aSubBlk && p->jtype!=aOptBlk ) p->lock[k] = FALSE;
  397. #ifdef DBG_TREES
  398.         fprintf(stderr, "blk(%s) returns:",((Junction *)p)->rname); preorder(r); fprintf(stderr, "\n");
  399. #endif
  400.         if ( r->down == NULL ) {tfree(r); return NULL;}
  401.         return r;
  402.     }
  403.  
  404.     if ( p->jtype==EndRule )
  405.     {
  406.         if ( p->halt )                        /* don't want FOLLOW here? */
  407.         {
  408.             set_orel(k, rk);                /* indicate this k value needed */
  409.             t = tnode(EpToken);
  410.             t->v.rk = k;
  411.             return t;
  412.         }
  413.         require(p->lock!=NULL, "rJunc: lock array is NULL");
  414.         if ( p->lock[k] ) return NULL;
  415.         /* if no FOLLOW assume k EOF's */
  416.         if ( p->p1 == NULL ) return eofnode(k);
  417.         p->lock[k] = TRUE;
  418.     }
  419.  
  420.     if ( p->p2 == NULL )
  421.     {
  422.         TRAV(p->p1, k, rk,t);
  423.         if ( p->jtype==EndRule ) p->lock[k]=FALSE;
  424.         return t;
  425.     }
  426.     TRAV(p->p1, k, rk, t);
  427.     if ( p->jtype!=RuleBlk ) TRAV(p->p2, k, rk, u);
  428.     if ( p->jtype==EndRule ) p->lock[k] = FALSE;/* unlock node */
  429.  
  430.     if ( t==NULL ) return tmake(tnode(ALT), u, NULL);
  431.     return tmake(tnode(ALT), t, u, NULL);
  432. }
  433.  
  434. Tree *
  435. tRuleRef(p,k,rk_out)
  436. RuleRefNode *p;
  437. int k;
  438. set *rk_out;
  439. { 
  440.     int k2;
  441.     Tree *t, *u;
  442.     Junction *r;
  443.     set rk, rk2;
  444.     char save_halt;
  445.     RuleEntry *q = (RuleEntry *) hash_get(Rname, p->text);
  446.     
  447. #ifdef DBG_TRAV
  448.     fprintf(stderr, "tRuleRef: %s\n", p->text);
  449. #endif
  450.     if ( q == NULL )
  451.     {
  452.         TRAV(p->next, k, rk_out, t);/* ignore undefined rules */
  453.         return t;
  454.     }
  455.     rk = rk2 = empty;
  456.     r = RulePtr[q->rulenum];
  457.     if ( r->lock[k] ) return NULL;
  458.     save_halt = r->end->halt;
  459.     r->end->halt = TRUE;        /* don't let reach fall off end of rule here */
  460.     TRAV(r, k, &rk, t);
  461.     r->end->halt = save_halt;
  462. #ifdef DBG_TREES
  463.     fprintf(stderr, "after ruleref, t is:"); preorder(t); fprintf(stderr, "\n");
  464. #endif
  465.     t = tshrink( t );
  466.     while ( !set_nil(rk) ) {    /* any k left to do? if so, link onto tree */
  467.         k2 = set_int(rk);
  468.         set_rm(k2, rk);
  469.         TRAV(p->next, k2, &rk2, u);
  470.         t = tlink(t, u, k2);    /* any alts missing k2 toks, add u onto end */
  471.     }
  472.     set_orin(rk_out, rk2);        /* remember what we couldn't do */
  473.     set_free(rk2);
  474.     return t;
  475. }
  476.  
  477. Tree *
  478. tToken(p,k,rk)
  479. TokNode *p;
  480. int k;
  481. set *rk;
  482. {
  483.     Tree *t;
  484.     require(constrain>=fset&&constrain<=&(fset[LL_k]),"tToken: constrain is not a valid set");
  485.  
  486.     constrain = &fset[maxk-k+1];
  487.  
  488. #ifdef DBG_TRAV
  489.     fprintf(stderr, "tToken(%d): %s\n", k, TerminalString(p->token));
  490.     if ( ConstrainSearch ) {
  491.         fprintf(stderr, "constrain is:"); s_fprT(stderr, *constrain); fprintf(stderr, "\n");
  492.     }
  493. #endif
  494.     if ( ConstrainSearch )
  495.         if ( !set_el(p->token, *constrain) )
  496.         {
  497. /*            fprintf(stderr, "ignoring token %s(%d)\n", TerminalString(p->token),
  498.                             k);*/
  499.             return NULL;
  500.         }
  501.     if ( k == 1 ) return tnode(p->token);
  502.     TRAV(p->next, k-1, rk, t);
  503.     /* here, we are positive that, at least, this tree will not contribute
  504.      * to the LL(2) tree since it will be too shallow, IF t==NULL
  505.      */
  506.     if ( t == NULL )    /* tree will be too shallow */
  507.     {
  508.         return NULL;
  509.     }
  510. #ifdef DBG_TREES
  511.     fprintf(stderr, "tToken(%d)->next:",k); preorder(t); fprintf(stderr, "\n");
  512. #endif
  513.     return tmake(tnode(p->token), t, NULL);
  514. }
  515.  
  516. Tree *
  517. tAction(p,k,rk)
  518. ActionNode *p;
  519. int k;
  520. set *rk;
  521. {
  522.     Tree *t;
  523.     
  524.     /*fprintf(stderr, "tAction\n");*/
  525.     TRAV(p->next, k, rk, t);
  526.     return t;
  527. }
  528.  
  529. /* see if e exists in s as a possible input permutation (e is always a chain) */
  530. int
  531. tmember(e,s)
  532. Tree *e, *s;
  533. {
  534.     if ( e==NULL||s==NULL ) return 0;
  535.     /*fprintf(stderr, "tmember(");
  536.     preorder(e); fprintf(stderr, ",");
  537.     preorder(s); fprintf(stderr, " )\n");*/
  538.     if ( s->token == ALT && s->right == NULL ) return tmember(e, s->down);
  539.     if ( e->token!=s->token )
  540.     {
  541.         if ( s->right==NULL ) return 0;
  542.         return tmember(e, s->right);
  543.     }
  544.     if ( e->down==NULL && s->down == NULL ) return 1;
  545.     if ( tmember(e->down, s->down) ) return 1;
  546.     if ( s->right==NULL ) return 0;
  547.     return tmember(e, s->right);
  548. }
  549.  
  550. /* combine (? (A t) ... (A u) ...) into (? (A t u)) */
  551. Tree *
  552. tleft_factor(t)
  553. Tree *t;
  554. {
  555.     Tree *u, *v, *trail, *w;
  556.  
  557.     /* left-factor what is at this level */
  558.     if ( t == NULL ) return NULL;
  559.     for (u=t; u!=NULL; u=u->right)
  560.     {
  561.         trail = u;
  562.         v=u->right;
  563.         while ( v!=NULL )
  564.         {
  565.             if ( u->token == v->token )
  566.             {
  567.                 if ( u->down!=NULL )
  568.                 {
  569.                     for (w=u->down; w->right!=NULL; w=w->right) {;}
  570.                     w->right = v->down;    /* link children together */
  571.                 }
  572.                 else u->down = v->down;
  573.                 trail->right = v->right;        /* unlink factored node */
  574.                 tfree( v );
  575.                 v = trail->right;
  576.             }
  577.             else {trail = v; v=v->right;}
  578.         }
  579.     }
  580.     /* left-factor what is below */
  581.     for (u=t; u!=NULL; u=u->right) u->down = tleft_factor( u->down );
  582.     return t;
  583. }
  584.  
  585. /* remove the permutation p from t if present */
  586. Tree *
  587. trm_perm(t,p)
  588. Tree *t, *p;
  589. {
  590.     /*
  591.     fprintf(stderr, "trm_perm(");
  592.     preorder(t); fprintf(stderr, ",");
  593.     preorder(p); fprintf(stderr, " )\n");
  594.     */
  595.     if ( t == NULL || p == NULL ) return NULL;
  596.     if ( t->token == ALT )
  597.     {
  598.         t->down = trm_perm(t->down, p);
  599.         if ( t->down == NULL )                 /* nothing left below, rm cur node */
  600.         {
  601.             Tree *u = t->right;
  602.             tfree( t );
  603.             return trm_perm(u, p);
  604.         }
  605.         t->right = trm_perm(t->right, p);    /* look for more instances of p */
  606.         return t;
  607.     }
  608.     if ( p->token != t->token )                /* not found, try a sibling */
  609.     {
  610.         t->right = trm_perm(t->right, p);
  611.         return t;
  612.     }
  613.     t->down = trm_perm(t->down, p->down);
  614.     if ( t->down == NULL )                     /* nothing left below, rm cur node */
  615.     {
  616.         Tree *u = t->right;
  617.         tfree( t );
  618.         return trm_perm(u, p);
  619.     }
  620.     t->right = trm_perm(t->right, p);        /* look for more instances of p */
  621.     return t;
  622. }
  623.  
  624. /* add the permutation 'perm' to the LL_k sets in 'fset' */
  625. void
  626. tcvt(fset,perm)
  627. set *fset;
  628. Tree *perm;
  629. {
  630.     if ( perm==NULL ) return;
  631.     set_orel(perm->token, fset);
  632.     tcvt(fset+1, perm->down);
  633. }
  634.  
  635. /* for each element of ftbl[k], make it the root of a tree with permute(ftbl[k+1])
  636.  * as a child.
  637.  */
  638. Tree *
  639. permute(k)
  640. int k;
  641. {
  642.     Tree *t, *u;
  643.     
  644.     if ( k>LL_k ) return NULL;
  645.     if ( ftbl[k][index[k]] == nil ) return NULL;
  646.     t = permute(k+1);
  647.     if ( t==NULL&&k<LL_k )        /* no permutation left below for k+1 tokens? */
  648.     {
  649.         index[k+1] = 0;
  650.         (index[k])++;            /* try next token at this k */
  651.         return permute(k);
  652.     }
  653.     
  654.     u = tmake(tnode(ftbl[k][index[k]]), t, NULL);
  655.     if ( k == LL_k ) (index[k])++;
  656.     return u;
  657. }
  658.  
  659. /* Compute LL(k) trees for alts alt1 and alt2 of p.
  660.  * function result is tree of ambiguous input permutations
  661.  *
  662.  * ALGORITHM may change to look for something other than LL_k size
  663.  * trees ==> maxk will have to change.
  664.  */
  665. Tree *
  666. VerifyAmbig(alt1,alt2,ft,fs,t,u,numAmbig)
  667. Junction *alt1, *alt2;
  668. unsigned **ft;
  669. set *fs;                        /* set of possible ambiguities */
  670. Tree **t, **u;                    /* return constrained perm sets */
  671. int *numAmbig;                    /* how many ambigs were there */
  672. {
  673.     set rk;
  674.     Tree *perm, *ambig=NULL;
  675.     int k;
  676.  
  677.     maxk = LL_k;                /* NOTE: for now, we look for LL_k */
  678.     ftbl = ft;
  679.     fset = fs;
  680.     constrain = &(fset[1]);
  681.     index = (int *) calloc(LL_k+1, sizeof(int));
  682.     if ( index == NULL )
  683.     {
  684.         fprintf(stderr, ErrHdr, CurAmbigfile, CurAmbigline);
  685.         fprintf(stderr, " out of memory while analyzing alts %d and %d of %s\n",
  686.                         CurAmbigAlt1,
  687.                         CurAmbigAlt2,
  688.                         CurAmbigbtype);
  689.         exit(-1);
  690.     }
  691.     for (k=1; k<=LL_k; k++) index[k] = 0;
  692.  
  693.     rk = empty;
  694.     ConstrainSearch = 1;    /* consider only tokens in ambig sets */
  695.  
  696.     TRAV(alt1->p1, LL_k, &rk, *t);
  697.     *t = tshrink( *t );
  698.     *t = tflatten( *t );
  699.     *t = prune(*t, LL_k);
  700.     *t = tleft_factor( *t );
  701. /*    fprintf(stderr, "after shrink&flatten&prune&left_factor:"); preorder(*t); fprintf(stderr, "\n");*/
  702.     if ( *t == NULL )
  703.     {
  704. /*        fprintf(stderr, "TreeIncomplete --> no LL(%d) ambiguity\n", LL_k);*/
  705.         Tfree( *t );    /* kill if impossible to have ambig */
  706.         *t = NULL;
  707.     }
  708.  
  709.     TRAV(alt2->p1, LL_k, &rk, *u);
  710.     *u = tshrink( *u );
  711.     *u = tflatten( *u );
  712.     *u = prune(*u, LL_k);
  713.     *u = tleft_factor( *u );
  714. /*    fprintf(stderr, "after shrink&flatten&prune&lfactor:"); preorder(*u); fprintf(stderr, "\n");*/
  715.     if ( *u == NULL )
  716.     {
  717. /*        fprintf(stderr, "TreeIncomplete --> no LL(%d) ambiguity\n", LL_k);*/
  718.         Tfree( *u );
  719.         *u = NULL;
  720.     }
  721.  
  722.     for (k=1; k<=LL_k; k++) set_clr( fs[k] );
  723.  
  724.     ambig = tnode(ALT);
  725.     k = 0;
  726.     if ( *t!=NULL && *u!=NULL )
  727.     {
  728.         while ( (perm=permute(1))!=NULL )
  729.         {
  730. /*            fprintf(stderr, "chk perm:"); preorder(perm); fprintf(stderr, "\n");*/
  731.             if ( tmember(perm, *t) && tmember(perm, *u) )
  732.             {
  733. /*                fprintf(stderr, "ambig upon"); preorder(perm); fprintf(stderr, "\n");*/
  734.                 k++;
  735.                 perm->right = ambig->down;
  736.                 ambig->down = perm;
  737.                 tcvt(&(fs[1]), perm);
  738.             }
  739.             else Tfree( perm );
  740.         }
  741.     }
  742.  
  743.     *numAmbig = k;
  744.     if ( ambig->down == NULL ) {tfree(ambig); ambig = NULL;}
  745.     free( index );
  746.     /*fprintf(stderr, "final ambig:"); preorder(ambig); fprintf(stderr, "\n");*/
  747.     return ambig;
  748. }
  749.